SCHEDULING PARALLEL PROGRAM TASKS WITH NON-NEGLIGIBLE INTERTASK COMMUNICATIONS ON TO NUMA MULTIPROCESSOR SYSTEMS

The purpose of this paper is to examine the impact of scheduling parallel tasks onto non-uniform memory access (NUMA) shared-memory multiprocessor systems by considering non-negligible intertask communications and communication contentions. Communication contentions arise from the communication medium having insufficient capacity to serve all transmissions, thereby causing significant contention delays. Therefore, a new scheduling algorithm, herein referred to as the Extended Critical Path (ECP) algorithm is proposed. The proposed algorithm schedules parallel tasks by considering non-negligible intertask communications and the contentions among shared communication resources. Moreover, it ensures performance within a factor of two of the optimum for general directed acyclic task graphs (DATGs). Experimental results demonstrate the superiority of the ECP algorithm over the scheduling algorithms presented in previous literature.     

PERFORMANCE ANALYSIS OF TASK CLUSTERING HEURISTICS FOR SCHEDULING STATIC DAGS ON MULTIPROCESSOR SYSTEM*

CASS is a task management system that provides facilities for automatic grain-size optimization and task scheduling of parallel programs on distributed memory parallel architectures. The heart of CASS is a clustering module that partitions the tasks of a program into clusters that match the granularity of the target machine. This paper describes the clustering algorithms used by CASS and compares them with the best known algorithms reported in the literature, namely the PY algorithm (for clustering with task duplication) and the DSC algorithm (for clustering with no task duplication). It is shown that the clustering algorithms used by CASS outperform both the PY and DSC algorithms in terms of both speed and solution quality.     

COMPUTING MAXIMUM CLIQUES OF CIRCULAR ARCS IN PARALLEL*

Given a set S of n proper circular arcs, it is required to identify a largest cardinality subset K[S] of S each two of whose members intersect. This paper describes an optimal parallel algorithm to compute K[S]. The algorithm is not based on any previously known sequential solution, and is designed for the CREW PRAM model of computation. It uses 0(n/logn) processors and runs in O(logn) time. An interesting feature of the algorithm is that it transforms the computational geometric problem at hand, to a problem involving computations on 0-1 matrices, and then transforms the latter back into a ray shooting problem in computational geometry.     

锡膏激光扫描三维测量系统光强自适应调节技术

根据锡膏激光扫描三维测量系统在测量PCB电路板时底板和锡膏对激光光强的散射效果不同,设计并研制了一套光强自适应调节光源。该光源以程控电源为基础,分析光条中心提取效果与激光光强的关系,应用小波分解与频带能量比相结合的光强自适应调节算法实现测量系统光强自适应调节功能。进行了相关实验,实验结果表明该光源能够很好地实现锡膏激光扫描三维测量系统的激光光强自适应调节,并能选出最适合测量的激光光强,具有很好的适用性。     

无线传感器网络中d-Hop 2-连通容错支配集的分布式构造算法

无线传感器网络随节点移动组成自我维持的自组织系统,采用连通支配集的虚拟骨干技术可使平面网络系统层次化而简化节点路由、管理和维护。但大规模无线传感器网络的连通支配集节点数目依然庞大,d-hop连通支配集可以大大减小支配集节点数目。另外,由于存在节点失效、链路断裂等无线特性,虚拟骨干网需要具备一定的容错性。在单位圆盘图网络模型中为构建精简且具有容错能力的虚拟骨干网,提出d-hop 2-连通支配集的分布式构造算法,先构造d-hop独立支配集后再连通形成d-hop 2-连通支配集。并从理论和仿真上对算法的复杂度、近似比和算法性能作了进一步探讨和验证。     

基于ＥＥＭＤ域统计模型的话音激活检测算法

提出了一种基于EEMD域统计模型的话音激活检测算法。算法首先利用总体平均经验模态分解(Ensemble empirical mode decomposition,EEMD)对带噪语音进行分解,得到信号的本征模式函数(Intrinsicmode function,IMF)分量,选择与原信号的相关性最高的两个分量相加组成主分量;然后对主分量进行频域分解,引入统计模型,求出EEMD域特征参数;最后利用噪声与语音的EEMD域特征参数的不同来进行语音激活检测。实验结果表明,在不同信噪比情况下,本文算法性能优于目前常用的VAD算法,特别在噪声强度大时体现出明显的优势。     

基于局部积分均值的经验模态分解改进算法

端点效应和模态混叠现象是经验模态分解算法应用中存在的主要问题。在介绍标准经验模态分解算法的基础上,阐述了基于局部积分均值经验模态分解算法的基本原理,提出自适应的端点局部积分均值拟合线的拟合方法。改进算法通过距离相关度函数在待分解信号内部寻找与端点处信号变化趋势相关度最高的一段波形,并用此段波形的局部积分均值拟合线来重新刻画端点处的局部积分均值拟合线,将修正后的局部积分均值拟合线应用于EMD算法筛选过程中。仿真实验结果表明,改进算法有效抑制了模态混叠和端点效应现象,提高了分解的精度和可靠性。     

一种用于指针程序的形状分析方法

指针程序的分析一直是研究热点。本文提出一种基于形状图逻辑的形状分析方法,其中形状分析采用形状图来表达程序中指针的指向和相等关系,并用形状图逻辑来进行推理。形状图逻辑是一种把形状图看成有关指针的断言,并在此基础上对Hoare逻辑进行扩展而得到的程序逻辑。首先介绍所提出的形状图和形状图逻辑;然后在此基础之上,设计一种基于形状图逻辑的形状分析方法。     

利用二进制数算法寻找5个点的Ramsey图

用二进制数来表示完全图的各种组合,借助计算机编程可从完全图的各种组合中寻找出ramsey图。5个顶点的Ramsey图是最基本的Ramsey图,这种基本方法为寻找更复杂的Ramsey图提供了基础。     

基于多模态推理图神经网络的场景文本视觉问答模型

文本阅读能力差和视觉推理能力不足是现有视觉问答(visual question answering, VQA)模型效果不好的主要原因,针对以上问题,设计了一个基于图神经网络的多模态推理(multi-modal reasoning graph neural network, MRGNN)模型。利用图像中多种形式的信息帮助理解场景文本内容,将场景文本图片分别预处理成视觉对象图和文本图的形式,并且在问题自注意力模块下过滤多余的信息;使用加入注意力的聚合器完善子图之间相互的节点特征,从而融合不同模态之间的信息,更新后的节点利用不同模态的上下文信息为答疑模块提供了更好的功能。在ST-VQA和TextVQA数据集上验证了有效性,实验结果表明,相比较此任务的一些其他模型,MRGNN模型在此任务上有明显的提升。